package leetcode101.tree;

/**
 * @author Synhard
 * @version 1.0
 * @class Code29
 * @description 450. 删除二叉搜索树中的节点
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
 * 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
 *
 * 示例:
 *
 * root = [5,3,6,2,4,null,7]
 * key = 3
 *
 *     5
 *    / \
 *   3   6
 *  / \   \
 * 2   4   7
 *
 * 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 *
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 *
 *     5
 *    / \
 *   4   6
 *  /     \
 * 2       7
 *
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 *
 *     5
 *    / \
 *   2   6
 *    \   \
 *     4   7
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-29 9:04
 */
public class Code29 {
    public static void main(String[] args) {

    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        if (root.val == key) {
            return format(root);
        }
        dfs(root, key);
        return root;
    }

    private void dfs(TreeNode root, int key) {
        if (root == null) {
            return;
        }
        if (root.left != null && root.left.val == key) {
            root.left = format(root.left);
            return;
        }
        if (root.right != null && root.right.val == key) {
            root.right = format(root.right);
            return;
        }
        dfs(root.left, key);
        dfs(root.right, key);
    }

    private TreeNode format(TreeNode root) {
        if (root.left == null && root.right == null) {
            return null; // 如果被删除的结点是叶节点，返回null即可
        }
        if (root.left != null && root.right != null) { // 如果是分支结点，并且拥有左孩子和右孩子的话
            TreeNode temp = root.left.right;
            root.left.right = root.right;
            TreeNode cur = root.left.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            cur.left = temp;
            return root.left;
        }
        if (root.left == null) {
            return root.right;
        }
        return root.left;
    }
}
